from typing import List


class Solution:
    import sys
    sys.setrecursionlimit(10000000)

    def __init__(self):
        inf = float('inf')
        self.min_level = inf
        self.max_level = -inf

    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:
        self.result = []

        def bat(array: list[int], ansl: list[int], ansr: list[int], level):
            n = len(array)

            if n <= 1:
                bat(ansl + array + ansr, [], [], level + 1)
                return
            if array[0] == firstPlayer and array[n - 1] == secondPlayer:
                self.min_level = min(self.min_level, level)
                self.max_level = max(self.max_level, level)
                return
            if array[0] == firstPlayer:
                bat(array[1:n - 1], ansl + [firstPlayer], ansr, level)
            elif array[n - 1] == secondPlayer:
                bat(array[1:n - 1], ansl, ansr + [secondPlayer], level)
            else:
                bat(array[1:n - 1], ansl + [array[0]], ansr, level)
                bat(array[1:n - 1], ansl, ansr + [array[n - 1]], level)

        bat(list(range(1, n + 1)), [], [], 1)
        return self.min_level, self.max_level


if __name__ == '__main__':
    s = Solution()
    r = s.earliestAndLatest(n=13, firstPlayer=2, secondPlayer=4)
    print(r)
